package com.fr.lintcode;

public class Q535 {
    /**
     * @param root: The root of binary tree.
     * @return: The maximum amount of money you can rob tonight
     */
    public int houseRobber3(TreeNode root) {
        // write your code here
    	if(root == null) {
    		return 0;
    	}
    	int v1 = search(root, 1);
    	int v2 = search(root, 2);
    	return v1 > v2 ? v1: v2;
  }

    
    private int search(TreeNode node , int states) {
    	if(node == null) {
    		return 0;
    	}
    	//抢劫当前节点
    	if (states == 1) {
    		int left = search(node.left,2);
    		int right = search(node.right,2);
    		int value = node.val + left + right;
    		return value;
    	}else if(states == 2) {//不抢劫当前节点,左右子节点可以抢或者不抢
    		int left = search(node.left,1);
    		int right = search(node.right,1);
    		int left1 = search(node.left,2);
    		int right1 = search(node.right,2);
    		left = left > left1 ? left : left1;
    		right = right > right1 ? right : right1;
    		return left + right;
    	}
    	return 0;
    }

}
